//假设一个无序数组里有若干个正整数，范围是1～100，其中有98个整数出现了偶数次，只有2个整数出现了奇数次，如何找到这2个出现奇数次的整数？”
//分治法

//把2个出现了奇数次的整数命名为A和B。遍历整个数组，然后依次做异或运算，进行异或运算的最终结果，等同于A和B进行异或运算的结果。在这个结果中，至少会有一个二进制位是1（如果都是0，说明A和B相等，和题目不相符）。”
//举个例子，给出一个无序数组{4，1，2，2，5，1，4，3}，所有元素进行异或运算的结果是00000110B。”


//选定该结果中值为1的某一位数字，如00000110B的倒数第2位是1，这说明A和B对应的二进制的倒数第2位是不同的。其中必定有一个整数的倒数第2位是0，另一个整数的倒数第2位是1。
//根据这个结论，可以把原数组按照二进制的倒数第2位的不同，分成两部分，一部分的倒数第2位是0，另一部分的倒数第2位是1。”
//由于A和B的倒数第2位不同，所以A被分配到其中一部分，B被分配到另一部分，绝不会出现A和B在同一部分，另一部分既没有A，也没有B的情况。”

//这样一来就简单多了，我们的问题又回归到了上一题的情况，按照原先的异或算法，从每一部分中找出唯一的奇数次整数即可。”
function findLostNum(arr) {
    let len = arr.length;
    // 1. 计算异或结果
    let xorResult = 0;
    for (let i = 0; i < len; i++) {
        xorResult ^= arr[i];
    }
    //如果进行异或运算的结果是0，则说明输入的数组不符合题意，直接返回null
    if (xorResult === 0) {
        return null;
    }
    console.log('xorResult:',xorResult) //6
    //2.确定2个整数的不同位，以此来做分组
    let separator = 1;
    while ((xorResult & separator) === 0) {
        separator <<= 1;
    }
    console.log('separator:',separator) // 2
    // 3. 第2次分组，进行异或运算
    let part1 = 0, part2 = 0;
    for (let i = 0; i < len; i++) {
        if ((arr[i] & separator) === 0) {
            part1^=arr[i];
        } else {
            part2^=arr[i];
        }
    }
    console.log(part1,part2)
    return [part1,part2]
}

let arr=[4,1,2,2,5,1,4,3]
console.log(findLostNum(arr))